﻿#include <iostream>
#include "../Matrix/Matrix.h"

static int recur(int n, int index, int prev)
{
    if (index >= n) return 1;

    int curIs0 = (index == 0 || prev == 0) ? 0 : recur(n, index + 1, 0);
    int curIs1 = recur(n, index + 1, 1);
    return curIs0 + curIs1;
}

static const int M[] = {
    1, 1,
    1, 0,
};

static int fibonacci(int n)
{
    switch (n)
    {
    case 1:
        return 1;

    case 2:
        return 2;

    case 3:
        return 3;
    }

    int f2_1[] = {
        fibonacci(2), fibonacci(1),
    };

    int* m = powMatrix(M, 2, 2, n - 2);
    int* resM = multiMatrix(f2_1, 1, 2, m, 2, 2);
    int res = resM[0];
    free(resM);
    free(m);
    return res;
}

//  字符串只由'0'和'1'两种字符构成
//  当字符串长度为1时，所有可能的字符串为"0", "1";
// 当字符串长度为2时，所有可能的字符串为"00", "01", "10", "11";
// 当字符串长度为3时，所有可能的字符串为"000", "001", "010", "011", "100", "101", "110", "111"
//  ...
//  如果某一个字符串中，只要是出现'0'的位置，左边就靠着'1', 这样的字符串叫做达标字符串。
//  给定一个正数N，返回所有长度为N的字符串中，达标字符串的数量。
//  比如，N = 3, 返回3，因为只有 "101", "110", "111"达标。
// 
// 思路:
// 方法1.可以用暴力递归->动态规划的做法来做
//  方法2.通过观察，N和返回值的关系契合裴波那契数列的规律.
//  即：
//  F(1) = 1
//  F(2) = 2
//  F(3) = 3
//  F(4) = 5
//  F(5) = 8
//  F(6) = 13
//  ...
// 
// 补充上F(0) = 1即为裴波那契数列。
int main_StringWithOnlyZeroAndOne()
{
    for (int n = 1; n <= 40; n++)
    {
        int f = recur(n, 0, 0);
        printf("F[%d]=%d\n", n, f);
        int f2 = fibonacci(n);
        printf("F[%d]=%d\n", n, f2);
    }

    return 0;
}